import java.util.Random;
/**
 * 
 * @author Olesse, and Shubert was also involved =)
 * Tests the insert and delete functions of your tree.
 * 
 * So it takes a random number between 0 and n and
 * inserts or deletes it from the tree - with probability
 * of 50% insert and 50% delete.
 * 
 * Then it checks whether the tree is valid.
 * If there is a problem in the tree, it prints which
 * action was the last and on which key.
 * 
 * This operation is repeating 100,000 times, every
 * time creates a new tree. In the end it prints num of
 * times that the tree was illegal.
 * 
 * We also used our homemade printTree function, to print the
 * tree and look for mistakes, you may replace it by your own.
 * 
 * Good luck :P
 */
public class TreeTest {

	public static void main(String[] args) {
		Random ran = new Random();
		int n = 40;
		int count = 0;
		
		for (int j = 0; j < 100000; j++) {
		RBTree tree = new RBTree();
		for (int i = 0; i < n; i++) {
			int r = ran.nextInt(n);
			int h = ran.nextInt(2);
			if(h==0){
				tree.insert(r, "");
				//RBTree.printTree(tree.root, 0);
				//System.out.println("");
			}
			else{
				//RBTree.printTree(tree.root, 0);
				//System.out.println("");
				tree.delete(r);
			}
			if(!tree.isValid()){
				count++;
				System.out.println("valid=" + tree.isValid() + " size=" + tree.size() +
						" action=" + h + " key=" + r);
				//RBTree.printTree(tree.root, 0);
				break;
			}
		}
		}
		System.out.println("\n"+count);
	}

}
